package main

import (
	"fmt"
	"math"
)

/*
题目3：求所有的逆序对

题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。
示例：
输入: [7,5,6,4]
输出: 5
*/
func main() {
	arr := []int{1, 3, 2, 3, 1}

	fmt.Println(arr)
	res := MergeSort2(arr)

	fmt.Println(arr, res)
}
func MergeSort2(arr1 []int) int {
	if arr1 == nil && len(arr1) < 2 {
		return 0
	}

	N := len(arr1)
	mergeSize := 1
	L := 0
	res := 0
	for true {
		L = 0
		for L < N {
			Mid := L + mergeSize - 1
			if Mid >= N {
				break
			}
			R := int(math.Min(float64(Mid+mergeSize), float64(N-1)))
			fmt.Println(L, Mid, R)
			res += Merge2(arr1, L, Mid, R)
			L = R + 1
		}
		if mergeSize > N/2 {
			break
		}
		mergeSize <<= 1
	}
	return res
}

func Merge2(arr []int, l, mid, r int) int {
	help := make([]int, r-l+1)

	p1 := l
	p2 := mid + 1
	i := 0
	res := 0
	for p1 <= mid && p2 <= r {

		if arr[p1] < arr[p2] {
			help[i] = arr[p1]
			p1++
			i++
		} else if arr[p2] < arr[p1] {
			help[i] = arr[p2]
			res += mid - p1 + 1 //核心代码只有当p2小于p1时p1剩余所有数都能和当前p2这个数构成逆序对
			p2++
			i++

		} else {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p2 > r {

		for p1 <= mid {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p1 > mid {

		for p2 <= r {
			help[i] = arr[p2]
			p2++
			i++
		}
	}

	for i, v := range help {
		arr[l+i] = v

	}
	return res

}
